/*
 * @lc app=leetcode.cn id=1125 lang=cpp
 *
 * [1125] 最小的必要团队
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
        std::vector<int> result;
        // (1)
        // 1 <= req_skills.length <= 16
        // no more than 16 skills
        // 0000000000000001
        using u16 = unsigned short;
        n = req_skills.size();
        peopleNum_ = people.size();
        int skillTarget = 0;
        for (int i=0;i<n;++i) {
            skillTarget += 1<<i;
        }
        // std::cout << "target" << std::endl;
        // std::cout << std::bitset<sizeof(u16)*8>(skillTarget) << std::endl;

        // (2)
        // 1 <= people.length <= 60
        // no more than 60 people
        // encode people set as u64
        using u64 = unsigned long;
        std::vector<std::map<u64, u16>> peopleSkillMapVec(1);
        // std::map<u64, u16> peopleSkillMap;

        // init
        for (int i=0;i<people.size();++i) {
            u64 peopleBin = 1<<i;

            auto& singlePeopleSkillString = people[i];
            for (int skillIndex=0;skillIndex<n;++skillIndex) {
                for (auto& skillString : singlePeopleSkillString) {
                    if (skillString == req_skills[skillIndex]) {                        
                        peopleSkillMapVec[0][peopleBin] += (1<<skillIndex);
                    }
                }
            }
            // wow, he is awesome ~
            if (peopleSkillMapVec[0][peopleBin] == skillTarget) {
                result.emplace_back(i);
                return result;
            }
        }

        // test show
        // for (auto& peopleSkillPair : peopleSkillMapVec[0]) {
        //     std::cout << std::bitset<sizeof(u16)*32>(peopleSkillPair.first) 
        //               << " "
        //               << std::bitset<sizeof(u16)*8>(peopleSkillPair.second) 
        //               << std::endl;
        // }

        // vecIndex = people_num - 1 = result_size - 1
        // let's add one people once in a loop
        for (int vecIndex=0;vecIndex<n-1;++vecIndex) {
            peopleSkillMapVec.emplace_back();
            auto& currentPeopleSkillMap = peopleSkillMapVec[vecIndex];
            auto& nextPeopleSkillMap = peopleSkillMapVec[vecIndex+1];
            
            for (auto& currentPeopleSet : currentPeopleSkillMap) {
                u64 currentTeamBin = currentPeopleSet.first;
                u16 currentTeamSkillBin = currentPeopleSet.second;

                // if (currentTeamBin == 1<<12 + 1<<23) {
                //     int checker = 1;
                // }

                for (int peopleIndex=0;peopleIndex<peopleNum_;++peopleIndex) {
                    u64 currentPeopleBin = 1<<peopleIndex;
                    u16 currentPeopleSkillBin = peopleSkillMapVec[0][currentPeopleBin];

                    // check if he has already joined current team
                    u64 newTeamBin = currentTeamBin | currentPeopleBin;
                    if (currentTeamBin == newTeamBin) {
                        continue;
                    }

                    // check if he contributes to current team
                    u16 newTeamSkillBin = currentTeamSkillBin | currentPeopleSkillBin;
                    if (currentTeamSkillBin == newTeamSkillBin) {
                        continue;
                    }

                    // check if achieved the skill target
                    if (newTeamSkillBin == skillTarget) {
                        GetPeopleIndexFromPeopleSetBin(newTeamBin, result);
                        return result;
                    }

                    // not yet, but now we know he is usefull for current team
                    nextPeopleSkillMap[newTeamBin] = newTeamSkillBin;
                }
            } 
        }
        
        return result;
    }
private:
    int n;
    int peopleNum_;
    void GetPeopleIndexFromPeopleSetBin(unsigned long teamBin, std::vector<int>& result) {
        using u64 = unsigned long;
        for (int peopleIndex=0;peopleIndex<peopleNum_;++peopleIndex) {
            u64 peopleBin = 1<<peopleIndex;
            u64 newTeamBin = teamBin | peopleBin;
            if (teamBin == newTeamBin) {
                result.emplace_back(peopleIndex);
            }
        }
    }
};
// @lc code=end

int main() {
    vector<string> req_skills = 
    {"mwobudvo","goczubcwnfze","yspbsez","pf","ey","hkq"};
    vector<vector<string>> people = 
    {{},{"mwobudvo"},{"hkq"},{"pf"},{"pf"},{"mwobudvo","pf"},{},{"yspbsez"},{},{"hkq"},{},{},{"goczubcwnfze","pf","hkq"},{"goczubcwnfze"},{"hkq"},{"mwobudvo"},{},{"mwobudvo","pf"},{"pf","ey"},{"mwobudvo"},{"hkq"},{},{"pf"},{"mwobudvo","yspbsez"},{"mwobudvo","goczubcwnfze"},{"goczubcwnfze","pf"},{"goczubcwnfze"},{"goczubcwnfze"},{"mwobudvo"},{"mwobudvo","goczubcwnfze"},{},{"goczubcwnfze"},{},{"goczubcwnfze"},{"mwobudvo"},{},{"hkq"},{"yspbsez"},{"mwobudvo"},{"goczubcwnfze","ey"}};

    Solution mySolution;
    mySolution.smallestSufficientTeam(req_skills, people);
}

// ["algorithms","math","java","reactjs","csharp","aws"]\n[["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
// ["mmcmnwacnhhdd","vza","mrxyc"]\n[["mmcmnwacnhhdd"],[],[],["vza","mrxyc"]]

